package com.sanra;

import java.util.ArrayList;
import java.util.Stack;

public class Tree {

    public static void main(String[] args) {
        TreeNode<String> A = new TreeNode<>("A");
        TreeNode<String> B = new TreeNode<>("B");
        TreeNode<String> C = new TreeNode<>("C");
        TreeNode<String> D = new TreeNode<>("D");
        TreeNode<String> E = new TreeNode<>("E");
        TreeNode<String> F = new TreeNode<>("F");
        TreeNode<String> G = new TreeNode<>("G");
        TreeNode<String> H = new TreeNode<>("H");
        TreeNode<String> I = new TreeNode<>("I");

        G.addLeft(H);
        G.addRight(I);
        D.addLeft(F);
        D.addRight(G);
        B.addLeft(D);
        B.addRight(E);
        A.addLeft(B);
        A.addRight(C);

        Traverse<String> traverse = new Traverse<>();
        traverse.preRecursion(A);
        traverse.print();
        traverse.reset();

        traverse.middleRecursion(A);
        traverse.print();
        traverse.reset();

        traverse.postRecursion(A);
        traverse.print();
        traverse.reset();


        traverse.preTraverse(A);
        traverse.print();
        traverse.reset();

        traverse.middleTraverse(A);
        traverse.print();
        traverse.reset();

        traverse.postTraverse(A);
        traverse.print();
        traverse.reset();


        int f = fibonacci(35);
        System.out.println(f);

        int optF = optFib(35);
        System.out.println(optF);
    }

    ///斐波那契数列计算
    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    ///优化版斐波那契数列计算
    ///已经计算过的就不再重复计算了，存储到一个数组里面，等用的时候从数组中取
    public static int optFib(int n) {
        int[] m = new int[n + 1];
        return helper(m, n);
    }

    public static int helper(int[] memo, int n) {
        if (n == 0 || n == 1) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
        return memo[n];
    }

    ///最佳斐波那契数列计算
    ///
    public static int bestFib(int n) {
        if (n == 0) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }


    public static class Traverse<T> {
        private final ArrayList<T> list = new ArrayList<>();

        public void reset() {
            list.clear();
        }

        public void print() {
            if (list.size() > 0) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < list.size(); i++) {
                    sb.append(list.get(i));
                    if (i < list.size() - 1) {
                        sb.append(",");
                    }
                }
                System.out.println(sb.toString());
            } else {
                System.out.println("列表为空");
            }
        }

        //前序遍历  (根左右)
        //递归实现
        public void preRecursion(TreeNode<T> root) {
            if (root != null) {
                list.add(root.val);
                preRecursion(root.left);
                preRecursion(root.right);
            }
        }

        //中序遍历  (左根右)
        //递归实现
        public void middleRecursion(TreeNode<T> root) {
            if (root != null) {
                middleRecursion(root.left);
                list.add(root.val);
                middleRecursion(root.right);
            }
        }

        //后序遍历 (左右根)
        //递归实现
        public void postRecursion(TreeNode<T> root) {
            if (root != null) {
                postRecursion(root.left);
                postRecursion(root.right);
                list.add(root.val);
            }
        }

        ///前序遍历
        ///非递归
        ///根左右
        public void preTraverse(TreeNode<T> treeNode) {
            Stack<TreeNode<T>> stack = new Stack<>();
            while (treeNode != null || !stack.isEmpty()) {
                while (treeNode != null) {
                    list.add(treeNode.val);
                    stack.push(treeNode);
                    treeNode = treeNode.left;
                }
                if (!stack.isEmpty()) {
                    treeNode = stack.pop();
                    treeNode = treeNode.right;
                }
            }
        }

        ///中序遍历
        ///非递归
        ///左根右
        public void middleTraverse(TreeNode<T> treeNode) {
            Stack<TreeNode<T>> stack = new Stack<>();
            while (treeNode != null || !stack.isEmpty()) {
                while (treeNode != null) {
                    stack.push(treeNode);
                    treeNode = treeNode.left;
                }
                if (!stack.isEmpty()) {
                    treeNode = stack.pop();
                    list.add(treeNode.val);
                    treeNode = treeNode.right;
                }
            }
        }

        ///后序遍历
        ///非递归
        /// 左右根
        public void postTraverse(TreeNode<T> treeNode) {
            Stack<TreeNode<T>> stack = new Stack<>();
            while (treeNode != null || !stack.isEmpty()) {
                while (treeNode != null) {
                    stack.push(treeNode);
                    treeNode = treeNode.left;
                }
                boolean tag = true;
                TreeNode<T> preNode = null;
                while (!stack.isEmpty() && tag) {
                    treeNode = stack.peek();
                    if (treeNode.right == preNode) {
                        treeNode = stack.pop();
                        list.add(treeNode.val);
                        if (stack.isEmpty()) {
                            return;
                        } else {
                            preNode = treeNode;
                        }
                    } else {
                        treeNode = treeNode.right;
                        tag = false;
                    }
                }
            }
        }
    }

    static class TreeNode<T> {
        T val;
        TreeNode<T> left;
        TreeNode<T> right;

        public TreeNode(T x) {
            this.val = x;
        }

        public void addLeft(TreeNode<T> left) {
            this.left = left;
        }

        public void addRight(TreeNode<T> right) {
            this.right = right;
        }
    }
}
